package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC730 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 对于此题，我还是保有疑问
     * @return:
     */
    class Solution {
        int MOD = (int) 1e9 + 7;

        public int countPalindromicSubsequences(String s) {
            char[] cs = s.toCharArray();
            int n = s.length();
            int[] L = new int[4], R = new int[4];
            int[][] f = new int[n][n];
            Arrays.fill(L, -1);
            // 通过从大到小的枚举方式枚举出 每个字符最靠左的位置
            for (int i = n - 1; i >= 0; i--) {
                L[cs[i] - 'a'] = i;
                Arrays.fill(R, -1);
                // 通过从当前字符最靠左的位置向右一直枚举找到当前字符位于最右侧的位置
                // 减少枚举次数
                for (int j = i; j < n; j++) {
                    R[cs[j] - 'a'] = j;

                    for (int k = 0; k < 4; k++) {
                        // 如果当前字符没有在字符当前 ij 区间中出现过 直接跳过
                        if (L[k] == -1 || R[k] == -1) continue;
                        int l = L[k], r = R[k];
                        // 如果此时字符串中 i,j 中 最靠左与最靠右的位置相同 则说明当前字符串当中出现的字符只有一个
                        // 他所能对 当前字符串的贡献只有 其 本身
                        if (l == r) f[i][j] = (f[i][j] + 1) % MOD;
                            // 如果此时当前字符的最左侧位置与最右侧位置只隔 1 说明 是两个紧挨着且相同的字符的同时
                            // 对源贡献为 k 或者 kk 均为回文子字符串
                        else if (l == r - 1) f[i][j] = (f[i][j] + 2) % MOD;
                        else f[i][j] = (f[i][j] + f[l + 1][r - 1] + 2) % MOD;
                    }
                }
            }
            return f[0][n - 1];
        }
    }

    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC730 an = new LC730();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
